WiMAX (Worldwide Interoperability for Microwave Access) is a cellular-based wireless multiple access standard, which is geared towards a series of applications, such as last mile broadband wireless connections, enterprise connectivity for businesses, and many others. Typical WiMAX base station (BS) installation will provide connections for subscriber stations (SS) within, for example, a five mile cell radius. The WiMAX standard defines several options for the physical layer (PHY), but the modulation of choice is typically Orthogonal Frequency Division Modulation (OFDM) or Orthogonal Frequency Division Multiple Access (OFDMA), details of which are found in the WiMAX physical layer specifications, IEEE Standard 801.16d, Part 16, “Air Interface for Fixed Broadband Wireless Access Systems”, and IEEE Standard 802.16e, Part 16, “Air Interface for Fixed and Mobile Broadband Wireless Access Systems”, both of which are incorporated herein by reference for all purposes. Although WiMAX is used in several of the examples provided herein, the present disclosure should in no way be limited to WiMAX or other wireless standards.
“Ranging” is a process by which a subscriber station (SS) initially synchronizes with the network, a process by which a SS remains synchronized to the network, a process by which a SS requests up-link (UL) bandwidth allocations, and a process by which a SS can handoff from one BS to another. A particular subscriber station uses the initial ranging process in order to register itself with a base station.
The ranging process is described as follows. A pre-defined set of 256 pseudo-noise “ranging codes” is divided into four groups: initial ranging, periodic ranging, bandwidth request ranging and handover. Each pseudo-noise ranging code has a length of 144 bits. A particular base station broadcasts in the downlink direction:                1) Ranging codes which are used for the initial ranging process, and        2) A ranging channel which contains 144 frequency subcarriers for the Ranging SS transmission.Whenever a subscriber station desires to register itself with a base-station, the subscriber station observes the broadcasted codes and randomly selects one code from the entire group. Note that this group has 256 elements at most. Upon selecting a ranging code, the subscriber station will modulate it across the 144 frequency subcarriers which were also defined by the base station. In turn, the base station will monitor the ranging channel and attempt to detect which ranging codes (out of 256 codes) are being transmitted by the subscriber stations in its sector. Furthermore, the base station will attempt to get initial delay estimates of each subscriber station which is trying to register.        
To complete the ranging procedure, the base station will next re-send the detected ranging code in the downlink direction. This ensures that the subscriber station knows that its registration is complete.
The 144 subcarriers which are dedicated for ranging are not typically a contiguous set of subcarriers but rather a distributed set across the available spectrum. In WiMAX, for example, they are partitioned into 36 groups of 4 contiguous subcarriers each. Each group of four contiguous subcarriers is called a “Tile.” Tiles are not contiguous between each other. The intent behind this system design strategy (non-contiguous tiles) is to provide SS transmission with frequency diversity, thereby combating the frequency-selective fading.
Subcarriers which are left blank are not used for the ranging process. Rather, their purpose is transmission of information, but only for subscribers which are already registered at the base station. The particular subscriber station which is currently registering will zero the values for those subcarriers.
Upon selecting a ranging code, a WiMAX compliant subscriber station will modulate it (the ranging code) across the 144 frequency subcarriers, using two OFDM symbols. Let N denote the total number of subcarriers within the WiMAX bandwidth. First, the (N−144) non-ranging subcarriers are filled with zeros. Second, the 144 ranging subcarriers are BPSK (Binary Phase Shift Keying) modulated with the selected ranging code. To compute the time-domain transmission, the inverse Fourier transform (IFFT) is taken for the entire sequence of length N. The result of the inverse Fourier transform is the time-domain signal, which we denote as X0 . . . XN−1. Once the IFFT signal has been computed, Ncp samples from the end of the time-domain signal are pre-pended to the N time-domain samples to form the cyclically shifted, time-domain signal. These N+Ncp samples are then transmitted by the subscriber station.
The figure has N=6 and Ncp=2 only for the sake of illustration. In general, the number N is a power of 2 so that the total number of samples within the OFDM symbol is a power of 2. Also, N is much larger (for example, N=2048). Also, the cyclic prefix above is shown having only two samples, but typically the cyclic prefix is only a fraction of the OFDM symbol (such as Ncp=N/4).
The subscriber station may be located anywhere within, for example, a five mile cell radius, away from the BS. Because of the propagation delay, the ranging transmission is not received timely at the base station. Rather, the BS will measure the delayed version of the ranging transmission. In turn, the Unknown Delay will correspond to the location of the subscriber station.
As seen on the above Example, the incoming ranging signal is received with an Unknown Delay at the base station. The Unknown Delay cannot be represented as an integer number of discrete samples because of the clock differences in the BS and Mobile Subscriber Station (MSS) and because of multi-path propagation of the transmitted signal. As a result, the Unknown Delay has certain delay spread associated with it. Therefore, the Unknown Delay presents a significant difficulty which prevents direct demodulation and detection. Upon measuring the received antenna signal, the task of the base station is to determine which ranging code is being used (if any) and furthermore, which delay does the code arrive with.
Since WiMAX is a non-profit organization working towards interoperability standards for broadband products and whose standards are a work in progress, most algorithms and solutions may be proprietary to various companies. One receive solution, however, is well-known time domain matched filter. With a time-domain matched filter, the received samples are passed through the filter whose impulse response if derived from the transmission itself. The peak output of the matched filter is detected, which gives the transmission delay. A well-documented problem with this solution is its complexity. In particular, the receiver would have to search over all ranging codes and all delays so that it would require 256 matched filters running in parallel. This solution turns out to be too intensive for current hardware. Other solutions, such as the Schmidl algorithm (for example), do result in a very low complexity receiver, but also impose a 3 dB noise enhancement.